package organizer;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Generic implementation of quick sort.
 * @author dawong
 */
public enum QuickSort {
    
    INSTANCE;
    
    public <V> void quicksort(IValueProvider<V> valueProvider, Comparator<V> comparator, List indexList) {
        quicksort(valueProvider, comparator, indexList, 0, indexList.size()-1);
    }

    private void quicksort(IValueProvider valueProvider, Comparator comparator,
            List indexList, int left, int right) {
        if (right > left) {
            int pivot = left + (right - left) / 2;
            int newPivot = partition(valueProvider, comparator, indexList, left, right, pivot);
            quicksort(valueProvider, comparator, indexList, left, newPivot-1);
            quicksort(valueProvider, comparator, indexList, newPivot+1, right);
        }

    }

    private <V> int partition(IValueProvider<V> valueProvider, Comparator<V> comparator,
            List indexList, int left, int right, int pivot) {
        V value = valueProvider.getValue(pivot);
        Collections.swap(indexList, pivot, right);
        int store = left;
        for (int i = left; i < right; i++) {
            V currVal = valueProvider.getValue(i);
            if (comparator.compare(currVal, value) <= 0) {
                Collections.swap(indexList, i, store);
                store++;
            }
        }
        Collections.swap(indexList, store, right);
        return store;
    }

    public static interface IValueProvider<T> {
        
        public T getValue(int i);
    }

}
